#include "graph.h"
#include <stdlib.h>
#include <stdio.h>

Graph CreateUndirectGraph(void)
{
    int N, i;
    Vertex v, w;
    Graph G;
    PtrToNode p;

    printf("Number of vertexes:");
    scanf("%d",&N);


    G = (Graph)malloc(sizeof(struct GraphRecord));
    G->vertices = (struct VertexRecord *)malloc(sizeof(struct VertexRecord) * (N + 1));
    G->vexnum = N;
    for (i = 1; i <= N; i++)
        G->vertices[i].adjto = NULL;


    printf("Number of edges:");
    scanf("%d",&N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d%d", &v, &w);
        p = ( struct Node *)malloc( sizeof( struct Node ) );
        p->adjvex = w;
        p->next = G->vertices[v].adjto;//p->next = _______________;
        G->vertices[v].adjto = p;//G->vertices[v].adjto = __________;
        p = ( struct Node *)malloc( sizeof( struct Node ) );
        p->adjvex = v;//p->adjvex = ________;
        p->next = G->vertices[w].adjto;//p->next = ___________;
        G->vertices[w].adjto = p;//G->vertices[w].adjto = _________;
    }
    return G;
}

void DestroyGraph(Graph G)
{
    /*free space*/
    if (G)
    {
        free(G->vertices);//_________;
        free(G);//_________;
    }
    return;
}

Vertex FirstAdjVex(Graph G, Vertex v)
{
    if (G->vertices[v].adjto)
        return G->vertices[v].adjto->adjvex;
    else
        return 0;
}

Vertex NextAdjVex(Graph G, Vertex v, Vertex w)
{
    PtrToNode p;

    p = G->vertices[v].adjto;
    while (p->adjvex != w)
        p = p->next;
    if (p->next)
        return p->next->adjvex;
    return 0;
}

int NumOfVex(Graph G)
{
    return G->vexnum;
}

void Shortest(Graph G, int S, int LAST[])
{
    Queue Q;
    int V, W, N;

    N = NumOfVex(G);
    for (V = 1; V <= N; V++)
        LAST[V] = 0;//LAST[V] = ________;//mark LAST as 0
    Q = CreateQueue(N);
    Enqueue(S,Q);//Enqueue(__________, Q);//enqueue the source into  Q
    while (!IsEmpty(Q))
    {
        V = Dequeue(Q);//V = __________;//takeoff one element from the Q
        for (W = FirstAdjVex(G, V); W; W = NextAdjVex(G, V, W))
            if ((W != S) && !LAST[W])//make sure W is not  visited
            {
                LAST[W] = V;//LAST[______] = _______;//
                Enqueue(W, Q);//Enqueue(________, Q);
            }
    }
    DisposeQueue(Q);
}







